#include <cstdio>
#include <cstring>
#include <map>
#include <string>

using namespace std;

map<string, int> m;
int n, maxl;

char Atoa( char a )
{
    if ( a >= 'A' && a <= 'Z' )
        return a - 'A' + 'a';
    return a;
}

void work( )
{
    int i, j, k, l, c;
    char str[ 200 ], p[ 200 ];
    string s;
    gets( str );
    for ( i = 0; i < n; i++ )
    {
        k = 0;
        gets( str );
        l = strlen( str );
        for ( j = 0; j < l; j++ )
            if ( str[ j ] >= 'a' && str[ j ] <= 'z' || str[ j ] >= 'A' && str[ j ] <= 'Z' )
                break;
        p[ k++ ] = Atoa( str[ j ] );
        for ( j = l - 1; !( str[ j ] >= 'a' && str[ j ] <= 'z' || str[ j ] >= 'A' && str[ j ] <= 'Z' ); j-- );
        for ( ; str[ j ] != ' '; j-- );
        for ( j++; j < l && k < maxl; j++ )
            if ( str[ j ] >= 'a' && str[ j ] <= 'z' || str[ j ] >= 'A' && str[ j ] <= 'Z' )
                p[ k++ ] = Atoa( str[ j ] );
        p[ k ] = 0;
        s = p;
        if ( m[ s ] )
        {
            c = m[ s ];
            m[ s ]++;
            if ( c < 10 && k == maxl )
                p[ k - 1 ] = 0;
            else if ( c >= 10 && k == maxl )
                p[ k - 1 ] = p[ k - 2 ] = 0;
            else if ( c >= 10 && k == maxl - 1 )
                p[ k - 1 ] = 0;
            printf("%s%d\n", p, c);
        }
        else
        {
            m[ s ]++;
            printf("%s\n", p);
        }
    }
}

int main( )
{
    int t = 1;
    while ( scanf("%d%d", &n, &maxl) )
    {
        if ( n == 0 && maxl == 0 ) break;
        m.clear( );
        printf("Case %d\n", t++);
        work( );
    }
    return 0;
}
